/*
 * Copyright (C), 2015-2018
 * FileName: Solution077
 * Author:   zhao
 * Date:     2018/12/18 18:58
 * Description: 77. 组合
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈77. 组合〉
 *
 * @author zhao
 * @date 2018/12/18 18:58
 * @since 1.0.1
 */
public class Solution077 {
    /**************************************
     * 题目
     给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     示例:

     输入: n = 4, k = 2
     输出:
     [
     [2,4],
     [3,4],
     [2,3],
     [1,2],
     [1,3],
     [1,4],
     ]
     **************************************/

    /*************************************
     想法：
        回溯算法： 以1起始数据，然后将2.3.4拼进去；
        再回头以2为起始位置，这时候就不能把1算进去，然后把3.4拼进去
     我的做法
     超过  %的测试案例
     时间复杂度/空间复杂度：  /
     代码执行过程：

     总结：

     ************************************/
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();

        List<Integer> cur = new ArrayList<>();

        dfs(n, k, 0, cur, ans);
        return ans;
    }

    private void dfs(int n, int k, int last, List<Integer> cur, List<List<Integer>> ans) {
        if (k == 0) {
            ans.add(new ArrayList<>(cur));
            return;
        }
        for (int i = last + 1; i <= n; i++) {
            cur.add(i);
            dfs(n, k - 1, i, cur, ans);
            cur.remove(i);
        }
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<Integer>> better(int n, int k) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (k > n) {
            return ret;
        }
        List<Integer> list = new ArrayList<Integer>();
        getpass(n, k, list, ret, 1);

        return ret;
    }

    public void getpass(int n, int k, List<Integer> list, List<List<Integer>> ret, int start) {
        if (list.size() == k) {
            ret.add(new ArrayList<Integer>(list));
            return;
        }
        int len = list.size();
        for (int i = start; i <= n; i++) {
            //加上下面着一个判断语句，速度就提高了很多，嘿嘿
            if (n - i < (k - len - 1)) {
                return;
            }
            list.add(i);
            getpass(n, k, list, ret, i + 1);
            list.remove(list.size() - 1);
        }
    }
}
